/**
 * @author tongchen
 * @create 2023-01-05 16:51
 */
public class Dynamic {


    public static void main(String[] args) {
        int[]ws={1,4,3};
        int[]val={1500,3000,2000};
        int w=4;
        int[][]v=new int[val.length+1][w+1];
        int[][]path=new int[val.length+1][w+1];
        //初始化
        for(int i=0;i<v[0].length;++i){
            v[0][i]=0;
        }
        //初始化
        for(int j=0;j<v.length;++j){
            v[j][0]=0;
        }
        //生成数组
        for(int i=1;i<v.length;++i){
            for(int j=1;j<v[0].length;++j){
                if(ws[i-1]>j){
                    v[i][j]=v[i-1][j];
                }else{
                    if(v[i-1][j]>v[i-1][j-ws[i-1]]+val[i-1]){
                        v[i][j]=v[i-1][j];
                    }
                    else{
                        v[i][j]=v[i-1][j-ws[i-1]]+val[i-1];
                        path[i][j]=1;
                    }
                }
            }
        }
        //打印数组
        for(int i=0;i<v.length;++i){
            for(int j =0;j<v[0].length;++j){
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }
        int i= path.length-1;
        int j=path[0].length-1;
        while(i>0&&j>0){
            if(path[i][j]==1){
                System.out.println("放入第"+i+"个商品");
                j-=ws[i-1];
            }
            i--;
        }
    }
}
